#include <iostream>
#include <vector>
using namespace std;

class Solution {
	int max_profit(vector<int> &prices)
	{
		int n = prices.size();
		vector<int> dp1(n, 0);
		vector<int> dp2(n, 0);
		int ans = 0;
		int min_price = prices[0];
		for (int i = 1; i < n; i++) {
			min_price = min(min_price, prices[i]);
			dp1[i] = max(dp1[i - 1], prices[i] - min_price);
		}

		vector<int> best(n, 0);
		best[0] = -prices[0];
		for (int i = 1; i < n; i++) {
			best[i] = max(best[i - 1], dp1[i] - prices[i]);
		}

		for (int i = 1; i < n; i++) {
			dp2[i] = max(dp2[i], best[i] + prices[i]);
			ans = max(ans, dp2[i]);
		}
		return ans;
	}

	int max_profit2(vector<int> &prices)
	{
		int n = prices.size();
		vector<int> dp1(n, 0);
		vector<int> dp2(n, 0);
		int ans = 0;
		int min_price = prices[0];
		vector<int> best(n, 0);
		best[0] = -prices[0];

                for(int i = 1; i < n; i++){
                        min_price = min(min_price, prices[i]);
                        dp1[i] = max(dp1[i - 1], prices[i] - min_price);
                        best[i] = max(best[i - 1], dp1[i] - prices[i]);
                        dp2[i] = max(dp2[i], best[i] + prices[i]);
                        ans = max(ans, dp2[i]);
                }
                return ans;
	}

        int max_profit3(vector<int> &prices)
        {
                int n = prices.size();
                int dp1 = 0, dp2 = 0, ans = 0, best = -prices[0];
                int min_price = prices[0];
                for(int i = 1; i < n; i++){
                        min_price = min(min_price, prices[i]);
                        dp1 = max(dp1, prices[i] - min_price);
                        best = max(best, dp1 - prices[i]);
                        dp2 = max(dp2, best + prices[i]);
                        ans = max(ans, dp2);
                }
                return ans;
        }

    public:
	int maxProfit(vector<int> &prices)
	{
		return max_profit3(prices);
	}
};

int main()
{
	vector<int> prices = { 3, 3, 5, 0, 0, 3, 1, 4 };
	cout << Solution().maxProfit(prices) << endl;
	return 0;
}